package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/24 12:52
 */
public class C377 {


    public static int combinationSum4(int[] nums, int target) {
        int ways = 0;
        for (int i = 0; i < nums.length; i++) {
            ways += ways(nums, i, target);
        }
        return ways;
    }

    public static int ways(int[] nums, int i, int rest) {
        if(i == nums.length) return rest == 0 ? 1 : 0;
        int ways = 0;
        for (int num = 1; num * nums[i] <= rest; num++) {
            ways += ways(nums, i + 1, rest - num * nums[i]);
        }
        return ways;
    }


    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int target = 4;
        System.out.println(combinationSum4(nums, target));
    }

}
